#include <iostream>
#include <tuple>
#include "linked_list.h"

using namespace std;

template <typename T>
LinkedList<T>::LinkedList(int capacity)
{
    this->cap = capacity;
    this->len = 0;
    this->head = new Node<T>();
    this->head->next = nullptr;
    this->head->prev = nullptr;
}

template <typename T>
void LinkedList<T>::Clear()
{
    this->len = 0;
    Node<T> *p = this->head->next;
    while (p != nullptr)
    {
        Node<T> *tmp = p->next;
        delete p;
        p = tmp;
    }
    this->head->next = nullptr;
}

template <typename T>
bool LinkedList<T>::IsEmpty() const
{
    return this->Len() == 0;
}

template <typename T>
bool LinkedList<T>::IsFull() const
{
    return this->Len() == this->cap;
}

template <typename T>
int LinkedList<T>::Len() const
{
    return this->len;
}

template <typename T>
tuple<bool, T> LinkedList<T>::Get(int index) const
{
    T element = T();
    if (index < 0)
    {
        index += this->len;
    }
    if (index < 0 || index >= this->len)
    {
        return make_tuple(false, element);
    }
    Node<T> *p = this->head->next;
    for (int i = 0; i < index; i++)
    {
        p = p->next;
    }
    return make_tuple(true, p->element);
}

template <typename T>
int LinkedList<T>::Find(T element) const
{
    Node<T> *p = this->head->next;
    int index = 0;
    while (p != nullptr)
    {
        if (p->element == element)
        {
            return index;
        }
        p = p->next;
        index++;
    }
    return -1;
}

template <typename T>
tuple<bool, T> LinkedList<T>::Prev(T element) const
{
    for (Node<T> *p = this->head->next; p != nullptr; p = p->next)
    {
        if (p->element == element && p->prev != nullptr)
        {
            return make_tuple(true, p->prev->element);
        }
    }
    return make_tuple(false, T());
}

template <typename T>
tuple<bool, T> LinkedList<T>::Next(T element) const
{
    for (Node<T> *p = this->head->next; p != nullptr; p = p->next)
    {
        if (p->element == element && p->next != nullptr)
        {
            return make_tuple(true, p->next->element);
        }
    }
    return make_tuple(false, T());
}

template <typename T>
bool LinkedList<T>::Insert(int index, T element)
{
    if (index < 0)
    {
        index += this->len;
    }
    if (index < 0 || index > this->len)
    {
        return false;
    }
    if (this->IsFull())
    {
        return false;
    }
    Node<T> *p = this->head;
    for (int i = 0; i < index; i++)
    {
        p = p->next;
    }
    Node<T> *new_node = new Node<T>();
    new_node->element = element;
    new_node->prev = p;
    new_node->next = p->next;
    if (p->next != nullptr)
    {
        p->next->prev = new_node;
    }
    p->next = new_node;
    this->len++;
    return true;
}

template <typename T>
tuple<bool, T> LinkedList<T>::Delete(int index)
{
    if (index < 0)
    {
        index += this->len;
    }
    if (index < 0 || index >= this->len)
    {
        return make_tuple(false, T());
    }
    Node<T> *p = this->head;
    for (int i = 0; i < index; i++)
    {
        p = p->next;
    }
    T element = p->next->element;
    p->next = p->next->next;
    if (p->next != nullptr)
    {
        p->next->prev = p;
    }
    delete p->next;
    this->len--;
    return make_tuple(true, element);
}

template <typename T>
bool LinkedList<T>::Remove(T element)
{
    Node<T> *p = this->head->next;
    while (p != nullptr)
    {
        if (p->element == element)
        {
            p->prev->next = p->next;
            if (p->next != nullptr)
            {
                p->next->prev = p->prev;
            }
            delete p;
            this->len--;
            return true;
        }
        p = p->next;
    }
    return false;
}

int main()
{
    // 创建一个整数类型的双向链表
    LinkedList<int> my_list(5);

    // 插入元素
    my_list.Insert(0, 10);
    my_list.Insert(1, 20);
    my_list.Insert(2, 30);

    // 获取元素
    cout << "Element at index 1: " << get<1>(my_list.Get(1)) << endl;

    // 查找元素的位置
    cout << "Index of element 20: " << my_list.Find(20) << endl;

    // 删除元素
    my_list.Delete(1);

    // 按值删除元素
    my_list.Remove(30);

    // 验证链表是否为空
    cout << "Is list empty? " << (my_list.IsEmpty() ? "Yes" : "No") << endl;

    // 验证链表是否已满
    cout << "Is list full? " << (my_list.IsFull() ? "Yes" : "No") << endl;

    // 清空链表
    my_list.Clear();

    return 0;
}
